# -*- coding: utf-8 -*-

"""薅羊毛：
双十一，满200减50活动，最大程度薅羊毛

动态规划，在计算到达到200门槛后最经济的薅毛成本（200? 201? 203?...）后,
并不需要通过反推的方法枚举出所有的商品搭配方案，只需要反推出一个方案即可。
不过可以在成本计算一致的情况下，如果方案存在多种，那么在反推时加入随机操作，这样每次计算得出的方案也会存在变化。

在下面场景中，商品量多，单价较低，总价在400多，在门槛不高的情况下如200，则要枚举的方案实在是太多了，时间复杂度简直是灾难，类似 O(2**n)。"""

from copy import deepcopy
from random import choice

def deal_getting(prices, threshold):
    uthreshold =  max(prices)+threshold

    # 传入的prices为可变列表，此处将实参修改，跳出函数时要注意
    prices.insert(0, 0)

    states = []
    ini_state = [False for _ in range(0, uthreshold+1)]
    
    start_state = deepcopy(ini_state)
    start_state[0] = True
    states.append(start_state)

    for i in range(1, len(prices)):
        cp = prices[i]
        cstate = deepcopy(ini_state)
        lstate = states[i-1]
        for tp, is_reach in zip(range(uthreshold+1), lstate):
            if is_reach:
                cstate[tp] = True

                if tp+cp <= uthreshold:
                    cstate[tp+cp] = True
        
        states.append(cstate)
    
    final_tp = 0
    for tp in range(threshold, uthreshold+1):
        if states[-1][tp]:
            final_tp = tp
            break
    
    if not final_tp:
        return
    
    # 枚举灾难 ***************************************************************************
    # schemes = Queue()
    # schemes.put((final_tp, []))

    # ids = list(range(1, len(prices)))
    # ids.reverse()
    # for i in ids:
    #     print(i)
    #     cp = prices[i]
    #     new_schemes = Queue()
    #     while True:
    #         try:
    #             scheme = schemes.get_nowait()
    #         except Empty:
    #             break
    #         tp, trace = scheme[0], scheme[1]
            
    #         if states[i-1][tp]:
    #             new_schemes.put((tp, deepcopy(trace)))
            
    #         if states[i-1][tp-cp]:
    #             newtrace = deepcopy(trace)
    #             newtrace.append(i)
    #             new_schemes.put(((tp-cp), newtrace))
        
    #     schemes = new_schemes
    # ************************************************************************************
    
    # 反推选择一个方案出来 -----------------------------------------------------------------
    scheme, tp = [], final_tp
    ids = list(range(1, len(prices)))
    ids.reverse()
    for i in ids:
        choose = []
        if states[i-1][tp]:
            choose.append(1)
        
        if tp-prices[i]>=0 and states[i-1][tp-prices[i]]:
            choose.append(2)
        
        r = choice(choose)

        if r == 1:
            pass
        elif r == 2:
            tp -= prices[i]
            scheme.append(i)
    
    scheme.reverse()

    return scheme, final_tp


if __name__ == '__main__':
    prices = [15,23,12,14,20,11,8,17,4,16,22,10,15,21,9,6,25,8,7,12,33,1,5,6,8,7,3,4,92]
    threshold = 200
    scheme, final_tp = deal_getting(prices, threshold)
    scheme_p = [prices[which] for which in scheme]
    print(scheme)
    print(scheme_p)
    print(final_tp, sum(scheme_p))
    # 可变prices在函数内部被修改
    # print(prices[29])
